package day1_array.leetcode.sliding_window;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: yuisama
 * @Date: 2022/9/10 14:52
 * @Description:滑动窗口解决字母异位词问题
 */
public class Num438_FindAnagrams {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        // p中不同字符哈希表
        int[] needs = new int[26];
        // 窗口中的字符哈希表
        int[] windows = new int[26];
        // p的有效键值对个数,以及窗口中有效键值对个数
        int validNeeds = 0,validWindow = 0;
        // 初始化needs哈希表
        for (int i = 0; i < p.length(); i++) {
            char c = p.charAt(i);
            if (needs[c - 'a'] == 0) {
                // 第一次出现字符c
                validNeeds ++;
            }
            needs[c - 'a'] ++;
        }
        int left = 0,right = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            right ++;
            windows[c - 'a'] ++;
            // 更新窗口
            // 当前字符c是要找的异位词之一的字符
            if (needs[c - 'a'] == windows[c - 'a']) {
                // 窗口中该字符出现的次数和需求字符串中出现次数相同
                // 窗口中有效键值对+1
                validWindow ++;
            }
            // 判断窗口左侧是否需要缩进
            if (right - left >= p.length()) {
                char d = s.charAt(left);
                // 更新窗口
                if (needs[d - 'a'] == windows[d - 'a']) {
                    if (validNeeds == validWindow) {
                        // 此时窗口中的有效键值对与需求字符串中有效键值对个数相同
                        // 当前窗口中的字符共同组成一个异位词
                        ret.add(left);
                    }
                    // 向前滑动时，窗口中有效键值对 - 1
                    validWindow --;
                }
                windows[d - 'a'] --;
                left ++;
            }
        }
        return ret;
    }
}
